#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
 *
 * TODO 这个题总觉得不是第一次写了 很快就秒写了类似于二叉树那个 但是现在写的是 二分那个
 * */
//挺神奇的根据二维数组推算一维数组 （二维数组转一维数组）
bool searchMatrix(vector<vector<int>> &matrix, int target) {
    //将二维矩阵看做一维

    int rowMax = matrix.size();
    int colMax = matrix[0].size();

    int left = 0;
    int right = rowMax * colMax - 1;

    // 0-11     mid =5   5/4，5%4

    while (left <= right) {

        int mid = (right - left) / 2 + left;

        //根据mid值在一维数组中的位置推出该值在二维数组的行列
        int row = mid / colMax;
        int col = mid % colMax;

        if (matrix[row][col] == target) {

            return true;

        } else if (matrix[row][col] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;

}
